/**
 * Created With IntelliJ IDEA
 * Description:牛客网：BM78 打家劫舍(一)
 * https://www.nowcoder.com/practice/c5fbf7325fbd4c0ea3d0c3ea6bc6cc79?tpId=295&tqId=2285793&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
 * User: DELL
 * Data: 2022-11-17
 * Time: 18:06
 */

//动态规划
import java.util.*;

public class Solution {
    public int rob (int[] num) {
        //题目中规定num数组不为空
        int len = num.length;
        if (len == 1) {
            return num[0];
        }
        //dp[i]表示打劫前i家获得的最大的现金金额
        int[] dp = new int[len];
        //初始化
        dp[0] = num[0];
        dp[1] = Math.max(num[0],num[1]);
        //递推公式：dp[i] = Math.max(dp[i-2] + num[i],dp[i-1]);
        for (int i = 2; i < len; i++) {
            dp[i] = Math.max(dp[i-2] + num[i],dp[i-1]);
        }
        return dp[len-1];
    }
}